
/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function (s, wordDict) {
  //定义状态数组dp
  let n = s.length
  let dp = new Array(n + 1).fill(false)
  dp[0] = true//空数组可以被拆分

  /* 遍历数组wordDict：比如遍历到索引i，再遍历索引j（0...j...i-1），如果dp[j]为true且s.substring(j,i)在字典wordDict中，dp[i]置true */
  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && wordDict.includes(s.substring(j, i))) {
        dp[i] = true
        break
      }
    }
  }

  //返回结果
  return dp[n]
};